package huawei.dstack;

import java.util.Stack;

/**
 * todo: 最优方法没看懂
 * https://leetcode-cn.com/problems/count-submatrices-with-all-ones/
 */
public class J1504 {
    public static void main(String[] args){
        System.out.println(numSubmat(new int[][]{{0,1},{1,1},{1,0}}));
        System.out.println(numSubmat(new int[][]{
                {1,0,1},
                {1,1,0},
                {1,1,0}
        }));
        System.out.println(numSubmat(new int[][]{
                {1,1,1,1,0},{1,0,0,1,0},{0,0,1,0,1},{0,1,0,0,0}
        }));
    }
    public static int numSubmat(int[][] mat) {
        int sum =0;
        int[][] dp = new int[mat.length][mat[0].length];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                if(mat[i][j]>0) {
                    dp[i][j] = 1;
                    if(j-1>=0){
                        dp[i][j]+=dp[i][j-1];
                    }
                }
            }
        }
        Stack<int[]> stack = new Stack<>();
        for (int i = 0; i < dp[0].length; i++) {
            stack.clear();
            int tmp=0;
            for (int j = 0; j < dp.length; j++) {
                int height = 1;
                while (!stack.isEmpty()&&dp[stack.peek()[0]][i]>dp[j][i]){
                    int[] last=stack.pop();
                    tmp-=(dp[last[0]][i]-dp[j][i])*last[1];
                    height+=last[1];

                }
                tmp+=dp[j][i];
                sum+=tmp;
                stack.push(new int[]{j,height});
            }
        }
        return sum;
    }
}
